/**
 * @author ChaP
 * @date 2019/06/30
 * @describe:
 */
package CodingTest.AC20190630;

import java.util.LinkedList;
import java.util.Queue;

/**leetcode - 513
 * 给定一个二叉树，在树的最后一行找到最左边的值。

 示例 1:

 输入:

 2
 / \
 1   3

 输出:
 1
  

 示例 2:

 输入:

 1
 / \
 2   3
 /   / \
 4   5   6
 /
 7

 输出:
 7
  

 注意: 您可以假设树（即给定的根节点）不为 NULL。
 *
 */
public class findBottomLeftValue {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x){val = x;}
    }
    public int findBottomLeftValue(TreeNode root){
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int result = root.val;
        while(!q.isEmpty()){
           int len = q.size();
           result = q.peek().val;
           for(int i = 0;i<len;i++){
               TreeNode temp = q.poll();
               if(temp.left!=null)  q.offer(temp.left);
               if(temp.right!=null) q.offer(temp.right);
           }
        }
        return result;
    }
}

